[Coding018] Sort - 插入排序

直接插入排序

More coding records

Get the knowledge flowing and circulating! :)

目录

标题：直接插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到${\displaystyle O(1)}$${\displaystyle O(1)}$的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

Insertion Sort 和打扑克牌时，从牌桌上逐一拿起扑克牌，在手上排序的过程相同。

举例：

输入： {3 5 6 7}。

首先拿起第一张牌, 手上有 {5}。

拿起第二张牌 3, 把 3 insert 到手上的牌 {5}, 得到 {3 5}。

拿起第三张牌 7, 把 7 insert 到手上的牌 {3 5}, 得到 {3 5 7}。

拿起第四张牌 6, 把 6 insert 到手上的牌 {3 5 7}, 得到 {3 5 6 7}。

以此类推。

具体实例执行过程

伪代码

Java代码实现

72
1
import java.util.Scanner;
2

3
// 这是一个类，名叫Solution
4
public class Solution {
5

6
    /**
7
     * 直接插入排序(Insertion Sort)
8
     */
9
    public static void main(String[] args) {
10
        // TODO Auto-generated method stub
11
        System.out.println("Hello, T!");
12

13
        Scanner input = new Scanner(System.in);
14

15
        int n = input.nextInt();
16

17
        int[] arr = new int[n];
18
        for (int i = 0; i < n; i++) 
19
        {
20
            arr[i] = input.nextInt();
21
        }
22

23
        for (int e : arr) 
24
        {
25
            System.out.print(e + " ");
26
        }
27
        System.out.println("\n--------------");
28

29
        Solution sol = new Solution();
30
        sol.insertSort_direct(arr, arr.length);
31

32
        for (int e : arr) 
33
        {
34
            System.out.print(e + " ");
35
        }
36
        return;
37
    }
38

39
    public void insertSort_direct(int[] arr, int n) 
40
    {
41
        for (int i = 0; i < n; i++) {
42
            int x = arr[i]; // 取待插入元素【从前到后，依次取】（同时保存这个元素，不怕被覆盖）
43
            int j = i - 1; // 依次比较其前面的元素 和 当前这个元素的值
44
            while (j >= 0 && x < arr[j]) // 因为j要递减，所以这里要做个条件判断
45
            {
46
                // 依次移动这个元素
47
                arr[j + 1] = arr[j];
48
                j--;
49
            }
50
            // 在空出的位置，放上这个待插入元素
51
            arr[j + 1] = x;
52
        }
53
    }
54

55
}
56

57
/*
58

59
测试样例: 
60
5 
61
5 4 7 9 6
62

63
9 
64
65 70 75 80 85 60 55 50 45
65

66
10 
67
10 20 30 40 50 60 70 80 90 100
68

69
20 
70
12 54 63 54 87 52 49 32 65 48 90 27 30 65 3 9 6 14 18 0
71

72
 */

运行结果

重点代码段解读

复杂度分析

• （对于数组而言的插入排序）需要比较的次数（Number of comparisons）

  边界情况	分析过程	→	复杂度
  MIN	$(C_i{)}_{min}=1,i=1...n-1$$(C_i)_{min}=1, i = 1...n-1$ (already in order)	→	$C_{min}=n-1=O(n)$$C_{min}=n-1=O(n)$
  MAX	$(C_i{)}_{max}=i,i=1...n-1$$(C_i)_{max}=i, i = 1...n-1$ (in reverse order)	→	$C_{max}=\sum _{i=1}^{n-1}i=\frac{n(n-1)}{2}=O(n^2)$$C_{max}=\sum\limits_{i=1}^{n-1}i=\frac{n(n-1)}{2}=O(n^2)$

• （对于数组而言的插入排序）需要移动的次数（Number of movements）

  Same as comparisons!（和比较的次数一样）

★ 知识点积累 (LaTex)

※ LaTex基础积累

LaTex 分数：$\frac{1}{2}$$\frac{1}{2}$ $\frac{1}{2}$

LaTex 求和（左右）：$\sum _{i=1}^{n-1}i$$\sum_{i=1}^{n-1}i$ $\sum_{i=1}^{n-1}i$

LaTex 求和（上下）：$\sum _{i=1}^{n-1}i$$\sum\limits_{i=1}^{n-1}i$ $\sum\limits_{i=1}^{n-1}i$